a. Field of the Invention
The instant invention is directed toward an explanation generation system for a computer-aided decision support tool employing an inference system. More specifically, it relates to a computer-aided diagnosis support tool employing an inference system and an interactive multimodal explanation generation system therefor. The explanation generation system produces interactive multimodal explanations for the results generated by the inference system in the diagnostic support tool.
b. Background Art
A woman has a 1 in 8 chance of developing breast cancer in her lifetime. In 1995, an estimated 183,400 women in the United States were newly diagnosed with breast cancer, and 46,240 died of the disease. Screening mammography effectively detects early breast cancers and can increase the likelihood of cure and long-term survival. Differentiating between benign and malignant mammographic findings, however, is difficult, with approximately 75% of mammograms classified xe2x80x9cindeterminate.xe2x80x9d
Successful diagnosis depends on the ability of a physician to detect mammographic abnormalities and to integrate clinical information such as risk factors and physical findings to determine the likelihood of breast cancer. Only 15%-30% of biopsies performed on nonpalpable but mammographically suspicious lesions prove malignant. Unnecessary biopsies are costly in terms of physical and emotional discomfort to the patient. Subsequent radiographic abnormalities from biopsies can be mistaken for cancer. Thus, the cost of screening mammography is increased.
Computer technology in the form of a clinical decision-support tool can be employed to improve the diagnostic accuracy and cost-effectiveness of screening mammography. Automated classification of mammographic findings using discriminant analysis and artificial neural networks (ANNs) has already indicated the potential usefulness of computer-aided diagnosis. ANNs learn directly from observations with a knowledge base of impenetrable numerical connection values. Although they perform well, ANNs do not provide for meaningful explanation generation.
Bayesian networksxe2x80x94also called belief networks or causal probabilistic networksxe2x80x94use probability theory as an underpinning for reasoning under uncertainty. One could use Bayesian networks as the formalism to construct a decision support tool. This tool integrated with a clinical database would provide accurate, reliable, and consistent diagnoses. A Bayesian network could perform a differential diagnosis by specifying the observed symptoms and computing the posterior probability of the various diagnoses using standard probability formulas.
Bayesian Networks provide a number of powerful capabilities for representing uncertain knowledge. Their flexible representation allows one to specify dependence and independence of variables in a natural way through a network topology. Because dependencies are expressed qualitatively as links between nodes, one can structure the domain knowledge qualitatively before any numeric probabilities need be assigned. The graphical representation also makes explicit the structure of the domain model: a link indicates a causal relation or known association. The encoding of independencies in the network topology admits the design of efficient procedures for performing computations over the network. A further advantage of the graphical representation is the perspicuity of the resulting domain model. Finally, since Bayesian networks represent uncertainty using standard probability, one can collect the necessary data for the domain model by drawing directly on published statistical studies.
A Bayesian belief networkxe2x80x94a graphical representation of probabilistic informationxe2x80x94is a directed acyclic graph. The graph is xe2x80x9cdirectedxe2x80x9d in that the links between nodes have directionality, that is, they are xe2x80x9cone way.xe2x80x9d The graph is xe2x80x9cacyclicxe2x80x9d in that it cannot contain cycles or xe2x80x9cfeedbackxe2x80x9d loops. The nodes of the network represent random variables (stochastic)xe2x80x94uncertain quantitiesxe2x80x94which take on two or more possible values or states. The states of a node define the set of possible values a node can be in at any one time. Each state is associated with a probability value; for each node, these probability values sum to 1. The states for any node are mutually exclusive and completely exhaustive. The directed links signify the existence of direct causal influences or class-property relationships between the connected nodes. The strengths of these nodes are quantified by conditional probabilities. In this formalism, variables are given numerical probability values signifying the degree of belief accorded them, and the values are combined and manipulated according to the rules of standard probability theory.
A Bayesian network contains two types of nodes: nodes with parents and nodes without. A node with at least one parent is represented graphically with a directed link connecting the parent node to the child node. In Bayesian terminology the parent node influences the child node. A node with a set of parents is conditioned on that parent set. A node with no parents is represented graphically with no directed links coming into the node. This latter type of node represents a prior probability assessment and is represented or quantified by an unconditioned prior probability representing prior knowledge.
The strengths of influences between the nodes are represented with conditional-probability matrices associated with the connecting links. For example, if node Z has two parent nodes X and Y, the conditional probability matrix specifies the probabilities of the possible values that Z can assume given all possible combinations of values that X and Y can assume.
The prior and conditional probability values used to build a Bayesian network can be derived directly from published values of sensitivity and specificity and collected from expert opinion.
The primary operation of a Bayesian network is the computation of posterior probabilities. A posterior probability of a variable is the probability distribution for this variable given all its conditioning variables. This inference operation consists of specifying values for observed variables, e.g., setting a node state to one, and computing the posterior probabilities of the remaining variables. The mathematics used in a Bayesian network is described as follows:
Let X be a random variable with n possible states, x1, . . . , xn. Let Y be a random variable with m possible states, y1, . . . , ym. The probability of a variable X, P(X), is a real number in the interval 0 to 1. P(X)=1 if and only if the event X is certain.
The probability of any event X being in state xi is denoted by
P(X=xi)=p, where p is the degree of belief accorded to X being in state xi.
The conditional probability of any event X being in state xi given a context Y is denoted by
P(X=xi|Y)=p, where p is the degree of belief accorded to X given the context Y.
The joint probability of any events X being in state xi and Y being in state yj is denoted by
P(X=xi, Y=yj)=p, where p is the degree of belief accorded to X=xi and Y=yj.
The probability distribution of a node X with possible states x1, x2, . . . , xn, is denoted by
P(X)=(x1, x2, . . . , xn), given xixe2x89xa70 and xcexa3xi=1, where xi is the probability of X being in state xi.
The product rule in probability is denoted by
P(X|Y)xc2x7P(Y)=P(X,Y).xe2x80x83xe2x80x83[1]
The probability distribution of X can be calculated from the joint probability distribution, P(X,Y), by summing over the partitions as denoted by                               P          ⁡                      (            X            )                          =                              ∑                          j              =              1                        m                    ⁢                      xe2x80x83                    ⁢                                    P              ⁡                              (                                  X                  ,                  Y                                )                                      .                                              [        2        ]            
The inversion formula (Bayes Theorem) in probability is denoted by
P(Y|X=e)=P(X=e|Y)xc2x7P(Y)/P(X=e), where e is user-observed evidence.xe2x80x83xe2x80x83[3]
A conditional probability distribution is all combinations of the variable X conditioned on its conditioning variable Y. The distribution will contain (number of possible states in X)xc2x7(number of possible states in Y) entries. For example, if X is a node with two possible states x1, x2 and Y is a node with three possible states y1, y2, y3, then P(X|Y) is the conditional probability table (vector) of size 2xc2x73=6 containing the real numbers P(xi|yj) denoted as shown in FIG. 1. For each state yi of Y, where i=1, . . . , n and j=1, . . . , m             ∑                        i          =          1                ,        …        ⁢                  xe2x80x83                ,        n              ⁢          xe2x80x83        ⁢          p      ⁡              (                              x            i                    |                      y            j                          )              =  1.
A joint probability distribution is all combinations of the variable X and the variable Y. The distribution will contain (number of possible states in X)xc2x7(number of possible states in Y) entries. The joint probability P(X,Y) is calculated using the product rule P(X|Y)xc2x7P(Y)=P(X,Y) as shown in FIG. 2. In FIG. 2, each value p(xi, yj) is p(xi, yj)xc2x7p(yj), for i=1, . . . , n and j=1, . . . , m
The sum of all the joint combinations equals 1.             ∑                        i          =          1                ,                  j          =          1                            n        ,        m              ⁢          xe2x80x83        ⁢          P      ⁡              (                  X          ,          Y                )              =  1
A shortcoming of Bayesian networks in automated medical reasoning is the difficulty users have understanding and trusting the systems. Physicians generally will not accept and act on a computer system""s advice without knowing the basis for the system""s decision. The users"" trust in these systems depends upon their ability to interact with the system and their ability to obtain understandable explanations. Although Bayesian networks are capable of xe2x80x9cexplainingxe2x80x9d their reasoning, which is an important advantage over ANNs, Bayesian networks are difficult to understand because they are composed of large numbers of numeric relationships that interact in nonintuitive ways. For any node N, each of its state values S can at once serve two purposes. It can represent a conclusion to be evaluated given some evidence E; P (N=S|E). It also can represent evidence for some other conclusion H; P (H|N=S). What emerge are chains of influence, corresponding to systems of conditional probability equations through which changes to probability values propagate. Additionally, numerical relations alone do not provide information about their origin. Thus, an effective computer-aided decision support tool employing an inference system must be able to generate explanations of its reasoning for the physicians and patients who use it.
It is desirable to be able to make medical diagnoses using an inference system that provides a meaningful explanation of its reasoning, preferably using an interactive multimodal explanation generation system.
Thus, the instant invention is a computer-aided decision support system including a reasoning component and an interactive multimodal explanation generation system. In one form, the reasoning component is a Bayesian network inference engine, and the interactive multimodal explanation generation system includes a multimodal interactive user interface for receiving multimodal inputs from a user and for presenting multimodal outputs to the user; a knowledge representation module in communication with the multimodal interactive user interface and with the Bayesian network inference engine; and a multimodal discourse module in communication with the knowledge representation module and with the multimodal interactive user interface. In another form, the multimodal discourse module comprises an explicit discourse history structure and an explanation component. In still another form, the multimodal interactive user interface comprises an input module and an output module, the input module in communication with the knowledge representation module, and the output module in communication with the multimodal discourse module.
In another form, the instant invention comprises a method of generating interactive multimodal explanations in a diagnostic support tool using a Bayesian network inference engine. In this form, the invention comprising the steps of waiting for an utterance from a user; constructing an input object from the utterance, the input object identifying a modality, a sequence, and a content of the utterance; inserting the input object into an input stream; sending the input stream to a knowledge representation module; and parsing and encoding the input object in the knowledge representation module into an abstract statement. In one form of this invention, the parsing and encoding step includes the steps of defining a statement type, defining a statement origin, defining a statement modality, and defining a statement context for each input object. The may then be communicated to a multimodal discourse module and stored in a discourse history structure. In yet another form, the invention further comprises the steps of generating an inquiry in the multimodal discourse module; communicating the inquiry to the knowledge representation module; processing the inquiry in the knowledge representation module; requesting probability calculations from the Bayesian network inference engine via the knowledge representation module based upon the processed inquiry; and passing the probability calculations to the multimodal discourse module.
In a third form, the instant invention comprises a method of generating interactive multimodal explanations during a dialog between system participants, including a decision support tool and a user, the decision support tool using a Bayesian network inference engine. In this form, the invention comprising the steps (A) receiving multimodal inputs from a user; (B) synthesizing the multimodal inputs into a single sequenced stream of events; (C) communicating the sequenced stream of events to a knowledge representation module; (D) generating, within the knowledge representation module, an abstract statement from the sequenced stream of events; and (E) storing the abstract statement into an explicit discourse history structure comprising part of a multimodal discourse module. In this form of the invention, step (D) may further comprise the steps of (i) syntactically processing the sequenced stream of events; (ii) semantically processing the sequenced stream of events; and (iii) contextually processing the sequenced stream of events. Alternatively, step (D) may further comprises the steps of (i) reading a lexicon file, comprising lexicon words and corresponding lexicon semantic word types; (ii) storing the lexicon words and corresponding lexicon semantic word types in a lexicon structure; (iii) parsing the sequenced stream of events into noun phrases and verb phrases; (iv) assigning a semantic type to each parsed phrase; (v) storing the parsed phrases and their assigned semantic phrase types in a chart data structure; (vi) comparing each stored parsed phrase and its assigned semantic phrase type from the chart data structure to the lexicon words and corresponding lexicon semantic word types stored in the lexicon structure trying to match patterns; and (vii) generating the abstract statement for matched patterns.
In a third form, the instant invention comprises a method of generating interactive multimodal explanations comprising the steps of receiving multimodal inputs from a user; synthesizing the multimodal inputs into a single sequenced stream of events; communicating the sequenced stream of events to a knowledge representation module; parsing and encoding the sequenced stream of events into an abstract statement; and using the abstract statement in reasoning tasks. The parsing and encoding step may further comprises the steps of syntactically, semantically, and contextually processing the abstract statement.
In a fifth form, the instant invention comprises a method of providing computer-aided decision support including the steps of initializing an inference engine; initializing a semantic network structure; initializing a discourse structure; initializing a parser; reading a lexicon file; waiting for user input; receiving multimodal inputs from a user; determining a type of input received; and processing the input based upon the determined type. If the type of input is evidence, it is processed by storing the evidence in an inference engine evidence vector; storing the evidence in a semantic network structure; determining a sensitivity based upon the evidence; and storing the determined sensitivity in the semantic network structure. If, on the other hand, the type of input is a Professor question, it is processed by determining which node is under consideration; interrogating the semantic network structure for node information; preparing the information for display; and constructing display specifications for displaying the information. Finally, if the type of input is a user question, it is processed by first determining whether the input is understood. If it is not understood, the input is processed by interrogating the discourse structure for context; formulating a clarifying question; and the clarifying question to the user. If, on the other hand, the question is understood, the input is processed by generating an abstract concept; storing the abstract concept in a discourse structure; and determining an action to take based upon the abstract concept. If risk information is desired, the system calculates the risk, displays it, and offers an explanation of the displayed result. If an explanation is desired, the system interrogates the discourse structure for context; interrogates the semantic network structure for an answer; constructs an explanation; and constructs display specifications for displaying the explanation.
A more detailed explanation of the invention is provided in the following description and claims, and is illustrated in the accompanying figures.